package com.muchfish.algorithm.linkedlist;

import com.muchfish.algorithm.linkedlist.pojo.ListNode;

/**
 * <a href="https://leetcode.cn/problems/reverse-linked-list/description/">题目：206. 反转链表</a>
 * <br>
 * 题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * <br>
 * <img src="https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg">
 * 解题思路：
 *
 */
public class LinkedList1 {
    public static void main(String[] args) {
        ListNode o = reverseList(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))));
        System.out.println("o = " + o);
    }

    /**
     * 反转链表（推荐）
     * @param head
     * @return
     */
    private static ListNode reverseList(ListNode head) {
        //反转链表，只需要反转链表的指针的指向就行
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    private static ListNode reverseList1(ListNode listNode) {
        //反转链表，只需要反转链表的指针的指向就行
        if (listNode != null) {
            //当前节点
            ListNode temp = listNode;
            //下一个节点
            ListNode next = listNode.next;
            //当前节点的下一个节点置为null
            temp.next = null;
            //将下一节点的后置节点指向当前节点即可
            while (next != null) {
                ListNode tempNext = next.next;
                next.next = temp;
                //下一节点作为当前节点
                temp = next;
                //下一节点的下一节点作为下一节点
                next = tempNext;
            }
            return temp;
        }
        return null;
    }

    /**
     * 递归反转链表
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            //此处return时，达到了原链表最后一个
            return head;
        }
        //newHead：原链表后一个 head：原链表前一个
        //head.next作为入参，相当于按原链表的顺序进行遍历
        //递归相当于出栈执行，先进先出，因此是从原链表的最后一个往前执行
        ListNode newHead = reverseList2(head.next);
        //head.next实际上是newHead，newHead.next指向head，完成了反转
        head.next.next = head;
        //head.next指向null，防止前后相互指，形成环
        head.next = null;
        return newHead;
    }



}

